package leetcode.code033;

public class Search2 extends Solution033 {

	@Override
	public int search(int[] nums, int target) {
		if (nums == null)
			return -1;
		int len = nums.length;
		if (len == 1)
			return nums[0] == target ? 0 : -1;
		if (len == 2)
			return nums[0] == target ? 0 : nums[1] == target ? 1 : -1;
		int l = 0;
		int r = len - 1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (nums[m] == target)
				return m;
			if (nums[m] >= nums[r] && target > nums[m]) {
				l = m + 1;
			} else if (nums[m] >= nums[r] && target < nums[m] && target < nums[l]) {
				l = m + 1;
			} else if (nums[m] >= nums[r] && target < nums[m] && target >= nums[l]) {
				r = m - 1;
			} else if (nums[m] < nums[r] && target > nums[m] && target > nums[r]) {
				r = m - 1;
			} else if (nums[m] < nums[r] && target > nums[m] && target <= nums[r]) {
				l = m + 1;
			} else if (nums[m] < nums[r] && target < nums[m]) {
				r = m - 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		Search2 search = new Search2();
//		search.debug1();
//		search.debug2();
//		search.debug3();
//		search.debug4();
		search.debug5();
	}

}
